package subjectlist;


public class P如何寻找最多的覆盖点 {


    public static int maxCover(int a[],int l){
        int count=0;
        int maxCount=1;//最长覆盖的点数
        int start=0;//覆盖坐标的起始位置
        int n=a.length;
        int i=0,j=1;
        while (i < n && j < n) {
            while ((j<n) && (a[j]-a[i]<=l)){
                j++;
                count++;
            }
            j--;
            count--;
            if (count > maxCount) {
                start=i;
                maxCount=count;
            }
            i++;
            j++;
        }
        System.out.println("覆盖的坐标点：");
        for (i = start; i <start+maxCount ; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        return maxCount;
    }

    /**
     *
     * 题目描述：坐标轴上从左到右依次的点为a[0]、a[1]、a[2]、…、a[n-1]，
     * 设一根木棒的长度为L，求L最多能覆盖坐标轴的几个点？
     *
     * 本题求满足a[j]-a[i]＜=L&&a[j+1]-a[i]＞L这两个条件的j与i中间的所有点个数中的最大值，即j-i+1最大，
     * 这样题目就简单多了。方法：直接从左到右扫描，使用两个索引i和j， i从位置0开始，j从位置1开始，如果a[j]-a[i] ≤ L，
     * 则j++前进，并记录中间经过的点的个数，如果a[j]-a[i]＞L，则j--回退，覆盖点个数-1，
     * 回到刚好满足条件的时候，将满足条件的最大值与前面找出的最大值比较，记录下当前的最大值，然后执行i++、j++，直到求出最大的点个数
     */
    public static void main(String[] args) {
        int a[]={-2,-1,3,7,8,3,11,12,20,15,16,17,19,25};
        System.out.println("最长覆盖点数:"+maxCover(a,8));
    }
}
